Systems exist whereby users can navigate through a computer-generated virtual environment such as, for example, a Virtual Reality (VR) environment, by repeatedly selecting predefined navigation points which correspond to a fixed set of viewing positions within the environment. In response to selecting a navigation point, the user's virtual position within the environment transitions to the selected navigation point, thereby allowing the user to view the environment from the viewing position that corresponds to the navigation point. The transition may be gradual (showing objects move past as the user “moves” through the environment), or instantaneous. The manner by which navigation points are selected by the user may vary based on a variety of factors, including the hardware being used to display the virtual environment.
For example, when viewing a virtual environment using a conventional computer, the navigation may involve manipulation of a cursor control device, such as a mouse or trackpad, and/or pressing keys of a keyboard. On the other hand, while wearing a VR headset, navigation may involve directing gaze, head movement, or a hand controller in a particular direction and then performing a navigation-triggering action. The navigation-triggering action may be operation of a control on the headset, on a handheld device that is engaged in wired or wireless communication with the headset, via a hand gesture, or merely by maintaining the gaze on a “navigation-point-marker” for more than a threshold period of time.
Navigation-point-markers are visual indicators, displayed within a virtual environment, of navigation points. Navigation-point-markers may take a variety of forms. For example, navigation point markers may simply appear as circles, spheres, or other shapes (e.g., a flag) floating in space within the virtual environment. Preferably, the navigation-point-markers are large enough to be detectable by a user that is navigating the virtual environment, but small enough so as not to obscure too much of the virtual environment or otherwise diminish the user's interactive virtual experience.
Techniques have been developed to create three-dimensional (“3D”) models based on photo images (and possibly 3D data) captured from a real-world environment. Such techniques are described, for example, in:                U.S. patent application Ser. No. 13/539,252 entitled “Capturing and aligning multiple 3-dimensional scenes”        U.S. patent application Ser. No. 13/776,688 entitled “Capturing and aligning three-dimensional scenes” Each of these documents is incorporated herein, in its entirety, by this reference.        
Once created, the 3D models may be navigated using navigation points in the manner described above. Under these circumstances, the navigation points will typically correspond to the image-capture positions that were used in the real-world environment to obtain the photo images upon which the 3D model is based. With some techniques, the images captured at the image-capture positions are panoramic, allowing the user to “look around” in the virtual environment in all directions.
For example, for a VR environment of a kitchen viewed by a user wearing a VR headset, the user may be able to see the kitchen sink when the user's head is in a neutral position, see the kitchen stove when the user turns her head to the right, and see the kitchen floor when the user tilts her head downward. In this example, the photo images of the kitchen sink, stove, and floor that the user sees can be captured at an image-capture position in the kitchen as part of a panoramic photo image capture process.
Unfortunately, some of the image-capture positions are likely to translate into undesirable navigation points. For example, some of the image-capture positions may be very close to walls or other large objects. Few people would intentionally navigate to such positions within the virtual environment, because few people would find those positions to be comfortable viewing positions, especially in VR environments where users can more easily become physically disoriented.
Proximity to a wall or other large object is merely one reason why some image-capture positions are not well-suited to be navigation points. Other examples of image-capture positions that are not well-suited to be navigation points include image-capture positions associated with low-quality photos, image-capture positions whose photo images do not capture anything particularly interesting, image-capture positions captured at unusually high or low heights, and image-capture positions whose photo images are largely redundant with the photo images of nearby image-capture positions.
Another problem with using every image-capture position as a navigation point is that, the denser the image-capture positions, the denser the navigation-point markers will be within the virtual environment. The greater the number of navigation-point markers, the greater the likelihood that seeing those markers will impair the user's virtual experience. For example, when viewing a bedroom in a virtual environment, a user will likely be annoyed or confused if fifty floating circles are displayed as navigation-point markers within the bedroom. In addition, densely packed navigation-points may require an unacceptably large number of navigation operations for a user to travel between points within the virtual environment.
To improve the virtual navigation experience, it is possible for users to manually designate which image-capture positions are to be used as navigation points in a virtual environment. However, when a large real-world environment is being modelled, a very large number of image-capture positions may be used to capture the photo images to create the model. As the size of the modeled environment and number of image-capture positions increase, so does the difficulty of manually selecting the optimal set of image-capture positions to be used as navigation points.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.